// 一元多项式
#include <stdio.h>
#include <stdlib.h>
typedef struct trem
{
    int exp;    //指数
    float coef; //系数
};
typedef struct list
{
    trem val;
    struct list *next;
};
// 创建多项式
void creat(list *&l, trem data[], int m)
{
    l = (list *)malloc(sizeof(list));
    list *r = l;
    for (int i = 0; i < m; i++)
    {
        if (data[i].coef == 0)
            continue;
        list *node = (list *)malloc(sizeof(list));
        node->val = data[i];
        r->next = node;
        r = node;
    }
    r->next = NULL;
}
void destroy(list *&l)
{
    if (l)
    {
        destroy(l->next);
        free(l);
    }
}

// a与b相加 销毁b
void add(list *&a, list *&b)
{
    list *p1 = a->next, *p2 = b->next, *h = a, *r = a;
    while (p1 && p2)
    {
        list *t;
        if (p1->val.exp == p2->val.exp)
        {
            t = p1;
            list *t2 = p2;
            t->val.coef += p2->val.coef;
            p1 = p1->next, p2 = p2->next;

            // 注意两个多项式可能会相互消去 两个节点均需要 free(节点)
            if (t->val.coef == 0)
            {
                free(t);
                t = NULL;
            }
            free(t2);
        }
        else if (p1->val.exp < p2->val.exp)
        {
            t = p1;
            p1 = p1->next;
        }
        else
        {
            t = p2;
            p2 = p2->next;
        }
        if (t)
        {
            r->next = t;
            r = t;
        }
    }
    if (p1)
        r->next = p1;
    if (p2)
        r->next = p2;
    free(b);
}
// a与b相减 销毁b
void sub(list *&a, list *&b)
{
    list *p1 = a->next, *p2 = b->next, *r = a;
    while (p1 && p2)
    {
        list *t;
        if (p1->val.exp == p2->val.exp)
        {
            t = p1;
            list *t2 = p2;
            t->val.coef -= t2->val.coef;
            if (t->val.coef == 0)
            {
                free(t);
                t = NULL;
            }
            p1 = p1->next;
            p2 = p2->next;
            free(t2);
        }
        else if (p1->val.exp < p2->val.exp)
        {
            t = p1;
            p1 = p1->next;
        }
        else
        {
            t = p2;
            t->val.coef *= -1;
            p2 = p2->next;
        }
        r->next = t;
        r = t;
    }
    if (p1)
    {
        r->next = p1;
    }
    while (p2)
    {
        p2->val.coef *= -1;
        r->next = p2;
        r = p2;
        p2 = p2->next;
    }
}
// a与b相乘 销毁b
void mul(list *&a, list *&b)
{
    for (list *p2 = b->next; p2 != NULL; p2 = p2->next)
    {
        for (list *p1 = a->next; p1 != NULL; p1 = p1->next)
        {
            p1->val.coef *= p2->val.coef;
            p1->val.exp += p2->val.exp;
        }
    }
    destroy(b);
}
void show(list *a)
{
    if (!a)
        return;
    list *p = a->next;
    while (p)
    {
        printf("%.3lf %d ", p->val.coef, p->val.exp);
        p = p->next;
    }
    printf("\n");
}
int main()
{
    /*******************code*******************/
    int c1[] = {7, 3, 9, 5};
    int e1[] = {0, 1, 8, 17};
    trem a1[4];
    for (int i = 0; i < 4; i++)
    {
        a1[i].exp = e1[i];
        a1[i].coef = c1[i];
    }
    int c2[] = {8, 22, -9};
    int e2[] = {1, 7, 8};
    trem a2[3];
    for (int i = 0; i < 3; i++)
    {
        a2[i].exp = e2[i];
        a2[i].coef = c2[i];
    }
    list *A, *B;
    creat(A, a1, 4);
    creat(B, a2, 3);
    show(A);
    show(B);
    // add(A, B);
    // sub(A, B);
    mul(A, B);
    show(A);
    /******************************************/
    fflush(stdin);

    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
